Corelab Seminar
2011-2012
Themis Gouleakis (NTUA)
Symmetric Lovasz Local Lemma and Satisfiability
Abstract.
In the first part of the talk, we will make a constructive proof of what symmetric LLL implies for SAT.
Namely, we are going to prove that the recent randomized algorithm proposed by R.Moser and G.Tardos can efficiently
find a satisfying assignment to any k-SAT instance (for any k) in which the maximum number of clause intersections
(a pair of clauses is called "intersecting" if they have a common variable) does not exceed a particular threshold. T
he expected running time is linear in the number of clauses (this guarantees the existence of the satisfying assignment).
The second part of the talk is about the (k,s)-SAT problem, a modification of k-SAT, which can be defined as follows: Given a
k-SAT formula F in which every variable appears at most s times, determine if F is satisfiable. For small values of s, this problem
is trivial (all instances are satisfiable). So, we can define f(k) to be the largest integer s for which (k,s)-SAT is trivial.
In a paper of J.Kratochvil,P.Savicky and Z.Tuza, it was proven that (k,f(k)+1)-SAT is NP-Complete despite the fact that (k,f(k))-SAT is
trivial by definition. We will demonstrate a proof of this result and show that f(k)=T((1/k)*2^k). The lower bound is achieved using the
Lovasz Local Lemma, implying that it is asymptotically tight. Moreover, it was recently shown by H.Gebauer ,T.Szabo and G.Tardos that the
value of f(k) is approximately: (2/e)(1/k)*2^k (up to an asymptotically smaller additive term). The factor (2/e) in the lower bound was again
proven using a stronger (lopsided) version of the LLL.